package com.cqs.leetcode.search;

import java.util.ArrayList;

public class Searcha2DMatrix74 {
    static class Solution {
        /**
         * 1. 折半查找行
         * 2. 定为到行后 折半查找
         *
         * @param matrix
         * @param target
         * @return
         */
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            int top = 0, bottom = matrix.length - 1;
            while (top <= bottom) {
                int mid = (bottom + top) / 2;
                if (matrix[mid][0] == target) return true;
                if (matrix[mid][0] < target) {
                    //先找到行
                    if (matrix[mid][matrix[0].length - 1] < target) {
                        //只可能在下面的行中
                        top = mid + 1;
                    } else {
                        //就在本行
                        int left = 0, right = matrix[0].length - 1;
                        while (left <= right) {
                            int m = (left + right) / 2;
                            if (matrix[mid][m] == target) return true;
                            if (matrix[mid][m] > target) right = m - 1;
                            else left = m + 1;
                        }
                        return false;
                    }
                } else {
                    bottom = mid - 1;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        ArrayList<int[][]> cases = new ArrayList<>();
        cases.add(new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}});

        cases.forEach(it -> {
            System.out.println(s.searchMatrix(it, 50));
        });
    }
}
